package com.leetcode;

/**
 * 322. 零钱兑换
 *
 * @author fy
 * @date 2022/3/29 22:13
 */
public class Solution322 {

    private int[] dp;
    private int maxAmount;

    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        int maxAmount = amount + 1;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = maxAmount;
        }
        for (int i = 0; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        int res = dp[amount];
        return res == maxAmount ? -1 : res;
    }

    /**
     * 322. 零钱兑换
     * <p>
     * coins = [1, 2, 5], amount = 11
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange1(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        dp = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            dp[i] = -1;
        }
        maxAmount = amount + 1;

        int res = searchCount(coins, amount);
        return res == maxAmount ? -1 : res;
    }

    private int searchCount(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (dp[amount] != -1) {
            return dp[amount];
        }
        int res = maxAmount;
        for (int coin : coins) {
            if (amount - coin >= 0) {
                res = Math.min(res, searchCount(coins, amount - coin) + 1);
            }
        }
        dp[amount] = res;
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{1, 2, 6};
        int amount = 11;
        System.out.println(new Solution322().coinChange(coins, amount));
    }
}
